package cn.hughie.sort;

import utils.SortUtils;

/**
 * 快速排序 和 归并排序一样都是由大到小 再由小到大
 *
 * @author yuh
 * @date 2018/5/15 13:15
 */
public class QuickSort {

    /**
     * 排序入口
     *
     * @param arr
     */
    public static void sort(Comparable[] arr) {
        //quickSort(arr, 0, arr.length - 1);
        threeWays(arr, 0, arr.length - 1);
    }

    /**
     * 快速排序
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void quickSort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = partition(arr, l, r);
        quickSort(arr, l, mid - 1);
        quickSort(arr, mid + 1, r);
    }


    /**
     * 二路切分
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static int partition(Comparable[] arr, int l, int r) {
        Comparable e = arr[l];
        int i = l + 1;
        int j = r;

        while (true) {
            while (i < r && SortUtils.largerThan(e, arr[i])) {
                i++;
            }
            while (j > l && SortUtils.largerThan(arr[j], e)) {
                j--;
            }
            if (i > j) {
                break;
            }
            SortUtils.swap(arr, i++, j--);
        }
        SortUtils.swap(arr, l, j);
        return j;
    }

    /**
     * 三路切分快排
     *
     * @param arr
     * @param l
     * @param r
     */
    public static void threeWays(Comparable[] arr, int l, int r) {

        if (l >= r) {
            return;
        }

        int lt = l;
        int gt = r + 1;
        int i = l + 1;
        Comparable e = arr[l];

        while (i < gt) {
            if (SortUtils.largerThan(arr[i], e)) {
                SortUtils.swap(arr, i, --gt);
            } else if (SortUtils.largerThan(e, arr[i])) {
                //小的交换位置一定是相等的
                SortUtils.swap(arr, i++, ++lt);
            } else {
                i++;
            }
        }
        SortUtils.swap(arr, lt, l);
        //从开始到lt前一位  因为lt刚被替换为本尊 前面才是比它小的
        threeWays(arr, l, lt - 1);
        //从gt开始到最后 gt也是比它大的
        threeWays(arr, gt, r);

    }

    public static void main(String[] args) {
        Integer[] arr = {2, 3, 4, 1, 3, 4, 52, 44, 41, 41, 41, 41, 4, 14, 141, 41, 14, 1, 41, 41, 4, 14};
        sort(arr);
        SortUtils.isSorted(arr);
    }
}